Marginalia — Cuaderno Interactivo Marginalia Notas: Sec. 3.1 — Introduction (TAOCP Vol. 2)
Proceso de lectura activa

La sección 3.1 introduce la utilidad fundamental de los números "elegidos al azar" en el ámbito de la ciencia de la computación y la simulación. A pesar de operar en sistemas inherentemente deterministas, la introducción de valores aleatorios es crucial para modelar la realidad, optimizar procesos y validar algoritmos.

a) Simulación

Se utilizan números aleatorios para dotar de realismo a la recreación digital de fenómenos naturales.

Un posible ejemplo se da en el modelado de colisiones de partículas en física nuclear o flujos de pasajeros en intervalos aleatorios en un aeropuerto (Investigación de Operaciones).

b) Muestreo (Sampling)

Cuando examinar un espacio muestral completo (todos los casos posibles) es computacionalmente inviable o prohibitivo en tiempo.

La solucion a esto es tomar un subconjunto aleatorio ("típico") para inferir el comportamiento general del sistema.

c) Análisis Numérico

Desarrollo de técnicas ingeniosas (como el método de Montecarlo) para resolver problemas matemáticos complejos y deterministas que carecen de una solución analítica sencilla, utilizando aproximaciones probabilísticas.

d) Programación de Computadores (Computer Programming)

Los datos aleatorios sirven como un banco de pruebas riguroso para evaluar la eficiencia y robustez de los algoritmos.

Estos son importantes ya que son la base para el desarrollo de algoritmos probabilísticos, los cuales superan en eficiencia a sus contrapartes puramente deterministas.

e) Toma de Decisiones (Decision making)

Permite realizar elecciones completamente imparciales ("unbiased").

Esto termina siendo importante ya que la aleatoriedad es una parte esencial para determinar las estrategias óptimas dentro de la teoría de juegos matriciales.

f) Criptografía (Cryptography)

El uso de bits aleatorios e imparciales es indispensable en la seguridad informática.

El proposito de esto esta en que se busca ocultar y proteger datos confidenciales a través de canales de comunicación seguros.

g) Estética (Aesthetics)

Una pequeña cantidad de aleatoriedad rompe la rigidez matemática exacta de los sistemas digitales.

Esto tinene un efecto ya que hace que los gráficos y la música generados por computadora cobren vida y parezcan más orgánicos y naturales.

Veamos un ejemplo en el gráfico de la sección g se ilustra de manera visual cómo la mente humana percibe e interpreta la aleatoriedad, contrastando un patrón estructurado frente a uno que introduce ligeras variaciones aleatorias.

aesthetics.png

Se muestra dos matrices de pequeños cuadrados contiguos colocados en filas y columnas:

  • Cuadrícula de la Izquierda (Patrón Determinista Rígido):

Muestra filas de cuadrados perfectamente alineados de manera geométrica y simétrica.

Cada cuadrado mantiene una posición exacta basada en coordenadas fijas, simulando una estructura matemática puramente predecible.

  • Cuadrícula de la Derecha (Patrón con Ruido Aleatorio o "Jitter"):

Muestra los mismos cuadrados, pero sus posiciones exactas en los ejes X e Y han sido sutilmente alteradas (desplazadas) de forma individual utilizando números aleatorios a pequeña escala.

Aunque la cuadrícula base sigue existiendo, los cuadrados individuales se ven ligeramente "desordenados" o descentrados.

El Concepto de Ruido Estético o "Jittering"

En los gráficos generados por computadora y el diseño de interfaces, la perfección absoluta de las líneas y los espaciados idénticos a menudo se percibe como fría, artificial, rígida o "computarizada". Al introducir una pequeña cantidad de aleatoriedad (un proceso conocido en informática visual como jitter o perturbación), se rompe la monotonía visual.

Impacto en la Percepción Humana

El patrón de la derecha "tende a verse más atractivo en ciertos contextos" (tends to look more appealing than [the other] in certain contexts). Esto se debe a dos razones fundamentales:

La primera de ellas es que en la naturaleza, las cosas rara vez se alinean con una precisión nanométrica perfecta. Las texturas naturales (la arena, las hojas, los tejidos artesanales) poseen pequeñas imperfecciones. La cuadrícula de la derecha imita esa naturalidad orgánica.

Mientras que en la segunda razon los patrones perfectamente repetitivos e idénticos fatigan rápidamente el sistema visual humano y pueden ser percibidos como aburridos o carentes de dinamismo.

Implementación del Modelo en Código (C)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

#define ANCHO_IMG 800
#define ALTO_IMG 400

#define FILAS 4
#define COLUMNAS 8
#define TAMANO_CUADRADO 30
#define DISTANCIA_PASO 45

void inicializar_lienzo(char lienzo[ALTO_IMG][ANCHO_IMG]);
void dibujar_cuadrado(char lienzo[ALTO_IMG][ANCHO_IMG], int x_ini, int y_ini);
void guardar_imagen_pbm(char lienzo[ALTO_IMG][ANCHO_IMG], const char *nombre_archivo);

int main() {
    static char lienzo[ALTO_IMG][ANCHO_IMG];
    inicializar_lienzo(lienzo);

    srand((unsigned int)time(NULL));

    int margen_izquierdo_X = 40;
    int margen_derecho_X = 440;
    int margen_Y = 120;
    int max_jitter = 10;

    for (int f = 0; f < FILAS; f++) {
        for (int c = 0; c < COLUMNAS; c++) {
            int x_base = margen_izquierdo_X + (c * DISTANCIA_PASO);
            int y_base = margen_Y + (f * DISTANCIA_PASO);

            dibujar_cuadrado(lienzo, x_base, y_base);
        }
    }

    for (int f = 0; f < FILAS; f++) {
        for (int c = 0; c < COLUMNAS; c++) {
            int x_base = margen_derecho_X + (c * DISTANCIA_PASO);
            int y_base = margen_Y + (f * DISTANCIA_PASO);

            int epsilon_x = (rand() % (2 * max_jitter + 1)) - max_jitter;
            int epsilon_y = (rand() % (2 * max_jitter + 1)) - max_jitter;

            int x_final = x_base + epsilon_x;
            int y_final = y_base + epsilon_y;

            dibujar_cuadrado(lienzo, x_final, y_final);
        }
    }

    guardar_imagen_pbm(lienzo, "imagenes/cuadriculas_knuth.pbm");

    return 0;
}

void inicializar_lienzo(char lienzo[ALTO_IMG][ANCHO_IMG]) {
    for (int y = 0; y < ALTO_IMG; y++) {
        for (int x = 0; x < ANCHO_IMG; x++) {
            lienzo[y][x] = 0;
        }
    }
}

void dibujar_cuadrado(char lienzo[ALTO_IMG][ANCHO_IMG], int x_ini, int y_ini) {
    for (int i = 0; i < TAMANO_CUADRADO; i++) {
        if (y_ini + i < ALTO_IMG && x_ini + i < ANCHO_IMG) {
            lienzo[y_ini][x_ini + i] = 1;
            lienzo[y_ini + TAMANO_CUADRADO - 1][x_ini + i] = 1;
        }
        if (y_ini + i < ALTO_IMG && x_ini + i < ANCHO_IMG) {
            lienzo[y_ini + i][x_ini] = 1;
            lienzo[y_ini + i][x_ini + TAMANO_CUADRADO - 1] = 1;
        }
    }
}

void guardar_imagen_pbm(char lienzo[ALTO_IMG][ANCHO_IMG], const char *nombre_archivo) {
    FILE *archivo = fopen(nombre_archivo, "w");
    if (archivo == NULL) {
        return;
    }

    fprintf(archivo, "P1\n");
    fprintf(archivo, "%d %d\n", ANCHO_IMG, ALTO_IMG);

    for (int y = 0; y < ALTO_IMG; y++) {
        for (int x = 0; x < ANCHO_IMG; x++) {
            fprintf(archivo, "%d ", lienzo[y][x]);
        }
        fprintf(archivo, "\n");
    }
    fclose(archivo);
}

imagenes/cuadriculas_knuth.pbm

h) Recreación (Recreation)

Actividades tradicionales como lanzar dados, barajar cartas o girar la ruleta dependen intrínsecamente del azar.

Esto tiene un impacto ya que estos usos lúdicos históricos dieron origen al término generalizado "Método de Montecarlo" para describir algoritmos basados en números aleatorios.

Conceptualización y Paradojas de la Aleatoriedad

Conceptualizar un único número aislado como "aleatorio" carece de sentido matemático (por ejemplo, el número 2 por sí solo no es aleatorio). En su lugar, se debe hablar de una secuencia de variables independientes con una distribución de probabilidad especificada.

Esto nos permite introducir de manera intuitiva el concepto de Distribución Uniforme, donde cada elemento dentro de un conjunto finito posee exactamente la misma probabilidad de ser seleccionado. Sin embargo, esto introduce comportamientos que a menudo chocan con la intuición humana y parecen paradójicos:

  • Desviaciones en muestras largas: En una secuencia verdaderamente aleatoria de un millón de dígitos, la probabilidad exacta de que aparezcan exactamente 100,000 ceros es sumamente baja. Las secuencias reales presentan fluctuaciones naturales.
  • Independencia de sucesos pasados: Si en una secuencia de un millón de dígitos los primeros 999,999 resultan ser cero, la probabilidad de que el último dígito sea un cero sigue siendo exactamente \(\frac{1}{10}\). El azar real no tiene memoria ni "compensa" rachas previas.

John von Neumann (1951)

"Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin." — JOHN VON NEUMANN (1951)

Me gustaria detenerme un poco en la célebre frase de von Neumann ya que expone la paradoja matemática fundamental de la generación de aleatoriedad en computación. Un algoritmo aritmético es, por definición, determinista: dada una misma semilla, producirá exactamente la misma secuencia de números. Por lo tanto, los números generados no son puramente "aleatorios" en el sentido físico o filosófico, sino pseudoaleatorios. Es por esto que Von Neumann califica con humor como "pecado" el pretender obtener caos puro a través del orden absoluto de la aritmética.

John Gay (1727)

"Lest men suspect your tale untrue, Keep probability in view." — JOHN GAY (1727)

John Gay en un tono poético subraya la relación entre la probabilidad y la verosimilitud dentro del modelado y la simulación. En el diseño de sistemas de software, si un modelo presenta resultados excesivamente perfectos o lineales, pierde credibilidad y utilidad práctica. La aleatoriedad controlada introduce los márgenes de desviación necesarios para que una simulación sea estadísticamente representativa del mundo real.

John Owen (1662)

"There wanted not some beams of light to guide men in the exercise of their Stocastick faculty." — JOHN OWEN (1662)

El término "facultad estocástica" (referente a lo conjetural o probabilístico). Cobra especial relevancia ya que Knuth la incluye para demostrar que la necesidad humana de entender, predecir y guiarse a través de variables aleatorias o inciertas ha existido desde siglos antes de la invención de las computadoras modernas. La ciencia de la computación simplemente formaliza esta "guía" mediante el software.

Sobre la Definición de Secuencia Aleatoria

"Rather, we speak of a sequence of independent random numbers with a specified distribution, and this means loosely that each number was obtained merely by chance, having nothing to do with other numbers of the sequence, and that each number has a specified probability of falling in any given range of values." pag. 2

Esta declaración establece la base matemática formal para trabajar con aleatoriedad en computación. Knuth busca redefinir el enfoque popular: la aleatoriedad no es una propiedad intrínseca del valor numérico final, sino una propiedad del proceso de generación y de la relación estadística entre los miembros de la serie. Para que una secuencia sea matemáticamente válida bajo este criterio, debe cumplir estrictamente con dos pilares: la independencia estadística mutua (falta de correlación) y la consistencia con una función de distribución de probabilidad preestablecida.

La Paradoja de las Probabilidades

"Thus, if we are choosing a million digits at random and if the first 999,999 of them happen to come out to be zero, the chance that the final digit is zero is still exactly 1/10, in a truly random situation. These statements seem paradoxical to many people, yet no contradiction is really involved." pag. 2

Queria citar esta parte porque aborda de forma directa lo que en psicología cognitiva y teoría de la probabilidad se conoce como la "falacia del apostador". La mente humana tiende a buscar patrones organizados y espera que los sistemas se auto-corrijan para forzar la simetría a corto plazo. Knuth aclara con rigor matemático que la probabilidad condicional de eventos verdaderamente independientes no se ve afectada por el histórico del sistema. La aparente paradoja no es una falla lógica del modelo matemático, sino un sesgo cognitivo del observador.

Evolución Histórica de la Generación de Aleatoriedad

a) Tablas y Dispositivos Mecánicos Tempranos

Inicialmente, la aleatoriedad se obtenía mediante tablas publicadas extraídas de censos o máquinas físicas basadas en ruido térmico/eléctrico.

Hitos cronológicos:

  • 1927: L. H. C. Tippett publica una tabla de más de 40,000 dígitos tomados de registros censales.
  • 1939: M. G. Kendall y B. Babington-Smith producen 100,000 dígitos usando una máquina electromecánica.
  • 1951: La computadora Ferranti Mark I incorpora hardware específico basado en un generador de ruido por resistencia eléctrica (sugerido por Alan Turing).
  • 1955: La corporación RAND publica su famosa tabla histórica de un millón de dígitos aleatorios.
  • ERNIE: Máquina utilizada en Gran Bretaña para seleccionar los números ganadores en sorteos de bonos estatales.

b) Limitaciones Fundamentales de los Métodos Físicos

Almacenar millones de dígitos en las memorias RAM/ROM primitivas de las computadoras consumía un espacio prohibitivo y restaba eficiencia a los programas.

Preparar, indexar y asegurar la correcta calibración de una máquina acoplada a la computadora (como ERNIE) era una tarea compleja y tediosa.

El defecto más crítico de conectar un dispositivo de ruido físico a una computadora es que hace imposible reproducir los cálculos exactamente de la misma manera. Esto destruye la capacidad de depurar (debuggear) el software cuando ocurre un fallo aleatorio.

Los componentes de hardware analógicos tienden a sufrir desviaciones sutiles por desgaste o temperatura, generando sesgos estadísticos extremadamente difíciles de detectar a simple vista.

c) El Renacimiento de las Tablas (Años 1990)

Con el abaratamiento radical del almacenamiento masivo, el problema de memoria desapareció.

George Marsaglia distribuye un CD-ROM con 650 megabytes de números aleatorios puros, combinando la salida de un circuito de diodo de ruido con música reproducida en un orden deterministamente caótico (bautizado como "ruido blanco y negro").

d) La Transición a Métodos Aritméticos

Ante la ineficacia de las soluciones físicas, la comunidad científica volcó su interés en generar números aleatorios mediante las operaciones aritméticas ordinarias de la propia CPU.

John von Neumann sugiere formalmente esta aproximación matemática alrededor del año 1946.

Método de los Cuadrados Medios (Middle-Square)

"John von Neumann first suggested this approach in about 1946; his idea was to take the square of the previous random number and to extract the middle digits." (Pág. 3)

El algoritmo germinal de la generación pseudoaleatoria computacional: el Método de los Cuadrados Medios. Von Neumann buscaba sustituir el hardware externo por funciones puramente matemáticas internas. El núcleo del algoritmo reside en mapear un valor inicial (semilla), elevarlo a una potencia aritmética exponencial de orden 2 (\(X^2\)) y aislar la sección central de la cadena de dígitos resultante para usarla como el siguiente número. Aunque metodológicamente elegante e innovador para su época, este algoritmo demostró ser inherentemente inestable a largo plazo, ya que tiende a colapsar rápidamente hacia ciclos repetitivos o a converger irreversiblemente hacia el valor cero (estado de muerte estocástica).

Objeción del Determinismo Aritmético

"There is a fairly obvious objection to this technique: How can a sequence generated in such a way be random, since each number is completely determined by its predecessor? … The answer is that the sequence isn't random, but it appears to be." (Pág. 3)

La línea divisoria epistemológica entre el azar ontológico y el azar operacional. Un sistema dinámico determinista de primer orden (donde el estado \(X_{n+1}\) depende estrictamente de una función \(f(X_n)\)) no puede producir aleatoriedad real bajo ninguna circunstancia. Sin embargo, para los propósitos prácticos de la ingeniería de software y la simulación, no se requiere caos absoluto, sino "apariencia de caos". La secuencia es considerada válida si y solo si supera con éxito una batería de pruebas estadísticas de independencia y distribución uniforme, comportándose operativamente de forma idéntica a una fuente de aleatoriedad física.

Validate